1. Field of the Invention
The invention relates to an automatic placement system and method for parts and, in particular, to an automatic parts placement system and method each of which is suitable to be used in, for example, a CAD (computer aided design) system automatically placing parts, figures, or the like on a plane.
2. Description of the Related Art
Some of parts placement methods applied to a previous printed wiring board or a previous semiconductor integrated circuit are disclosed in documents. For example, a parts placement optimizing method is disclosed in Japanese Laid Open Publication No. H06-332983 (namely, 332983/1994, U.S. Pat. No. 5,600,555). With this method, it is possible to determine, in a short time, parts placement which provides a comparatively low valuation standard, such as a total wiring length. Hereinafter, the document will be referred to as xe2x80x9cdocument 1xe2x80x9d. Specifically, the parts placement optimizing method virtually converts parts into uniform size of blocks or a set of blocks (initial placement), and replaces blocks in the blocks or in the set of blocks. As a result, the method improves the parts placement so that the valuation reference such as a total wiring length may become small as possible, and finally returns the virtually converted blocks to real parts.
The method may be implemented through a program in a computer system which includes an input device, such as a keyboard, a display device such as a CRT display, and a data processing device having a CPU, a memory, and a hard disk.
Further, disclosure is made in Japanese Laid Open Publication No. H03-108739 (namely, 108739/1991, U.S. Pat. No. 5,309,371) about an integrated circuit blocks placement method of placing variant size of blocks and determining a wiring between the blocks. The document will be, hereinafter, referred to as xe2x80x9cdocument 2xe2x80x9d.
The method initially places the blocks using a mass system spring model in which each of circuit blocks is assumed to be connected to the other circuit blocks by a spring with the block size neglected. It may be said that energy of the dynamic model corresponds to sums of squares of net lengths. Under the above-assumption, the initial placement is made such that the energy may become minimum by using a method of placing the parts in a gravity point (barycenter).
Then, the parts or circuit blocks are approximated by circles which have block sizes to calculate placement of each circle. Thereafter, the circles are transformed to the real configurations of the blocks to replace the blocks so that there are no overlaps among the blocks. In other words, the method compacts the blocks along with a frame of a circuit board and modifies the shape of each block from the circular figure to the actual shape.
Finally, the method assigns a zone for wiring by swelling the blocks and adjusts an aspect ratio of each block in a tolerance level.
Similarly, a method disclosed in Japanese Laid Open Publication No. H03-124046 (namely, 124046/1991, U.S. Pat. No. 5,309,371) utilizes the mass system spring model and performs the similar initial placement as described above. Herein, the document is referred to as xe2x80x9cdocument 3xe2x80x9d.
Furthermore, disclosure is made in Japanese Laid Open Publication No. H06-332984 (namely, 332984/1994) about an element placement method which is capable of determining an optimum solution in a short time without exchanging two elements. The document is, hereinafter, referred to as xe2x80x9cdocument 4xe2x80x9d.
The method comprises the steps of (1) determining a gravity point of each net, (2-1) determining an average vector by determining vectors from each terminal position and by averaging the vectors, (2-2) determining a position to which the element is moved based on the average vector, (3) determining a permutation of the elements according to coordinate values of the position, and (4) determining a matrix structured placement of the elements so that there are no overlaps between elements in consideration of the shapes of the elements and a matrix structured initial placement placing the elements according to the determined permutation.
As described above, the method of the document 1 determines an optimum parts placement so that the total wiring length becomes minimum. The total wiring length is defined as a sum of Manhattan distances between parts elements connected by the net.
On the other hand, the method of the document 2 and the method of the document 4 use the sums of squares of distances between the parts elements connected through the net to determine an optimum parts placement.
However, there is no analytical solution against a problem of finding the above optimum parts placement. Therefore, to find an optimum solution, a method has been adopted which selects a combination which has a minimum value among total wiring lengths obtained by calculating all combinations of possible parts placements.
But, the number of combinations becomes equal to N! (N is the number of the parts). In consequence, an amount of computations required to find the optimum solution increases explosively as the number N increases.
Therefore, parts placement algorithm of finding a solution close to an optimum solution in a short time has been developed.
As described above, the prior method of repeatedly selecting parts placement by exchanging parts so as to shorten its own total wiring length causes critical placements to occur such that no reduction is possible. There are often a plurality of critical parts placements. Once a solution is found which corresponds to such a critical parts placement, any other optimum solutions can not be found, although there is another optimum solution which leads to less total wiring length. This problem is known as local stabilization.
Here, to avoid the local stabilization and to determine an optimum solution, a simulated annealing method may be simultaneously used. The method applies a principle of leaving from a state of local stabilization using state transition of disturbance in heating a molecule, to search of parts placement. That is, some solutions are generated by random modification, and then, the most improved solution (for example, a solution which leads to less total wiring length) is selected among these solutions.
Also, a method has been known which improves a solution by repeating steps of generating xe2x80x9cdescendantxe2x80x9d solutions resulting from random disturbance of a part of initially obtained solutions based on genetic algorithm, and selecting the most improved solution among the xe2x80x9cdescendantxe2x80x9d solutions.
However, the parts placement system using the simulated annealing method or the genetic algorithm still has a problem that an operation time is incomparably larger than a time needed for determining a solution by the pair exchange method.
This is because the system using the simulated annealing method or the genetic algorithm has many and complex procedures. Specifically, the system generates a large number of solutions which are slightly different from each other using the random disturbance, determines improved solutions using the pair exchange method based on each of the generated solutions, generates a large number of solutions again by disturbing the improved solutions, and estimates the finally generated solutions.
There are two substantial points in the system. A first point is that the disturbance process should be performed appropriately and in a fully broad range not to miss a path to an optimum solution. A second point is that convergence process should be completely performed so as to converge the randomly disturbed solutions.
Consequently, to obtain a solution closer to an optimum solution, it is required to perform as much fully disturbance process as possible and perform complete convergence process to convergence the disturbance. Thus, if one would obtain more proper solution, a longer operation time is required.
On the other hand, in the methods disclosed in the document 2 through the document 4, since each of the methods uses the mass system spring model, a shorter operation time is realized. However, in the mass system spring model, it is not possible to distinguish a large size of block from a small size of block. In this case, there is a problem that a given solution does not reflect an influence from the size of the block.
Next, description is made about a second problem. The method of the document 4 (hereinafter, the method is referred to as xe2x80x9cgravity point methodxe2x80x9d), which places the parts in a gravity point of the net, does not always reach the shortest total wiring length. For example, assuming that a first part is connected to the leftmost of a substrate via two nets and connected to the rightmost of the substrate via a single net, a gravity point of the first part is placed in a position far from the leftmost of the substrate by the distance of ⅓ of the width of the substrate toward the rightmost of the substrate. Also, assuming that a second part is connected to the leftmost of a substrate via six nets and connected to the rightmost of the substrate via four nets, a gravity point of the second part is placed in a position far from the leftmost of the substrate by the distance of ⅖ of the width of the substrate toward the rightmost of the substrate. Therefore, the position of the gravity point of the second part is placed between the leftmost of the substrate and the gravity point of the first part.
Here, to obtain the shortest total wiring length, the second part should be located in the left side of the first part, since the difference between the number of the nets connected to the leftmost of the substrate and the number of the nets connected to the rightmost of the substrate is equal to two and therefore the difference is larger than that of the first part by 1.
However, the gravity point method can not provide a proper conclusion.
Further, in the gravity point method, since a contribution from a far side of terminal of a part is considered as proportionate to square of the distance, a weight from a far part is greater than a weight from a near part. Therefore, the method is not suitable to directly obtain parts placement which realizes a short total wiring length.
To overcome the first problem and the second problem, a method disclosed in Japanese Laid Open Publication No. H06-149939 (namely, 149939/1994, and referred to as xe2x80x9cdocument 5xe2x80x9d) has been proposed by the applicant of the invention.
The method considers the number of wiring from a part as attractive force and determines a (pseudo) parts specific gravity or relative weight by dividing the attractive force by an area of the part. Next, the method places parts on a single dimension in ascending order of the corresponding parts specific gravity. Thus, the method determines two one-dimensional parts placements and generates a two-dimensional parts placement (schematic parts placement) in which one of the one-dimensional parts placement is projected to the X-axis and the other is projected to the Y-axis. In other words, the method produces the optimum schematic parts placement (initial parts placement) by freely modifying placement of parts or a set of parts.
However, in the method, since the schematic parts placement is incomplete, it is not possible to design placement using only the schematic parts placement.
Therefore, it is an object of the invention to provide an automatic parts placement device and its method which are capable of placing parts in proper positions based on the schematic parts placement according to actual shapes of the parts, and completing parts placement which is possible to be directly used for subsequent design.
Further, it is another object of the invention to provide an automatic parts placement device and its method which are capable of performing calculation of parts placement which realizes the shortest total wiring length without repeating trial and error for exchanging of parts positions. Therefore, according to the automatic parts placement device and its method of the invention, calculation for placement of all the parts is performed once, and parts placement which is approximate to the shortest total wiring length is obtained in a short time.
Also, other objects, features, and merits will become clear from the following description.
Hereinafter, principles of the system according to the invention will be described. At first, position data of a plurality of position designated parts are supplied to the system. Then, parts are each added to one of parts groups each of which is generated based on one of the position designated parts using the supplied position data. This process is performed by the following steps (1) to (3).
(1) Determining Parts specific gravity or relative weight by dividing the number of nets which connect a part to a parts group, by the area of the part. The determined parts specific gravity is considered as actual specific gravity in physical phenomenon.
(2) Extracting a combination of a part and a parts group which provide the maximum parts specific gravity and adding the part to the parts group. Thus, parts groups are formed by adding parts around the position designated part.
(3) Repeating the addition process until all the parts are added to any one of the parts groups.
Also, in the above steps (1) to (3), each parts group is formed by grouping parts on the basis of a position designated part. But, in the other embodiment of the invention, each parts group may be determined by instructions from an input unit (such as a later described input unit 103 of the invention) in response to an operator.
Next, partitioned zones (hereinafter, referred to as xe2x80x9cpartitionsxe2x80x9d) each of which corresponds to a parts group are generated. Partitions are formed based on an area of the corresponding parts group.
Each partition has a rectangular shape. As mentioned before, the term xe2x80x9cpartitionxe2x80x9d means a partitioned section or zone on a two-dimensional plane of parts placement zone rather than a room in a three-dimensional space.
Then, parts specific gravity is calculated on two-dimensional plane of the X-Y coordinate for each partition. The parts specific gravity is calculated for an inclined line which descends rightwards at an angle of 45 degrees relative to the X axis (a first one-dimensional axis). That is, a sum of lengths of nets connecting between the parts is calculated by projecting the nets towards the inclined line and may be considered as potential. energy in physical phenomenon.
Placement which makes the total wiring length minimum is determined by calculating a first one-dimensional parts placement position which places the parts along the first one-dimensional coordinate in the descending order of the parts specific gravity. This means that a real physical phenomenon is simulated wherein placement for minimizing potential energy of materials is determined by placing materials in an order from heavier specific gravity to lighter one from downside position.
Then, like in the above process, parts specific gravity is calculated for another inclined line which ascends rightwards at an angle of 45 degrees relative to the X axis (a second one-dimensional axis, which is perpendicular to the first one-dimensional axis). And a second one-dimensional parts placement position is determined by placing the parts along the second one-dimensional coordinate in the descending order of the parts specific gravity.
Thereafter, from the first one-dimensional parts placement position and the second one-dimensional parts placement position for the parts, parts placement position on the two-dimensional plane is produced. One of the coordinate axes of the two-dimensional parts plane descends rightwards at an angle of 45 degrees relative to the X axis of the partition and is related to the first one-dimensional parts placement position. The other axis ascends rightwards at an angle of 45 degrees relative to the X axis of the partition and is related to the second one-dimensional parts placement position.
Then, parts groups each of which is placed on the two-dimensional plane are included in the corresponding partition. In the partition, the parts in the parts group are further placed.
A first method of placing the parts in the parts group includes the step of placing the parts in the partition by using compaction process.
A second method includes the steps of determining a quadrilateral shape which includes all the parts in the parts group (the shape of the quadrilateral is not limited to rectangular shape), transforming coordinate values to map the quadrilateral to the rectangular shape of partition, and determining parts placement position from the result of mapping.
Then, vertical division lines which divide the parts in the partition into left side parts and right side parts on the two-dimensional plane are produced. Further, horizontal division lines are produced to divide the parts in the partition into upside parts and downside parts on the two-dimensional plane. Next, the vertical and horizontal division lines are helpful to define zones each of which corresponds to a part in the partition according to the area of the part.
Then, the part is assumed to be placed in the center of the corresponding zone.
According to a first aspect of the invention, an automatic parts placement system is provided. The system comprises (1) a storage device which stores net data of a net connecting between terminals of parts, parts data, and position data of position designated parts, (2) a deriving unit which derives parts group from a plurality of parts, (3) a partition producing unit which divides a parts placement zone into a plurality of partitions according to the total area of all the parts in the parts group, each partition having a predetermined shape and being related to the parts group, (4) a parts specific gravity calculating unit which calculates, for each partition, a parts specific gravity of a undefined part by subtracting, from the number of nets connecting between placed parts and the undefined part in the partition, the number of the other nets connected to the undefined part, and by dividing the result of subtracting by the area of the undefined part, (5) a one-dimensional placing unit which places the undefined parts nearby the placed part in the descending order of the parts specific gravity on a first one-dimensional axis to produces a first one-dimensional parts placement, and which places the undefined parts adjacent to the placed part in the descending order of the parts specific gravity on a second one-dimensional axis perpendicular to the first one-dimensional axis to produces a second one-dimensional parts placement, and (6) a two-dimensional placing unit which places, for each partition, the undefined parts on a two-dimensional plane by using the first one-dimensional parts placement and the second one-dimensional parts placement.
Further, according to a second aspect of the invention, an automatic parts placement device which automatically places parts on two-dimensional parts placement zone is provided. The device comprises (1) a part data input device which inputs shapes and areas of the parts and net data of nets connecting between the parts, and stores them to a storage device, (2) an operational instruction input device which designates placement position of a position designated part in response to an operational instruction, (3) a cluster producing unit which produces a cluster including parts each of which has strong net connectivity, (4) a first parts specific gravity calculating unit which derives a parts specific gravity for each combination of a part and a parts group, (5) a parts group producing unit which adds a part to a parts group having a plurality of parts around the position designated part, (6) a re-distributing unit which moves a part from a current parts group to another parts group which has stronger connectivity to the part, (7) a partition producing unit which produces a rectangular shape of partition by dividing a parts placement zone according to a ratio of an area of the parts group, (8) a one-dimensional parts specific gravity calculating unit which calculates a parts specific gravity based on the number of nets connecting in the direction of a one-dimensional coordinate axis of the part, (9) a one-dimensional lining unit which lines the parts on a first one-dimensional coordinate axis in order of the parts specific gravity to store the parts placement as first one-dimensional parts placement, and lines the parts on a second one-dimensional coordinate axis perpendicular to the first one-dimensional coordinate axis in order of the parts specific gravity to store the parts placement as second one-dimensional parts placement, (10) a two-dimensional part placing unit which schematically places the part using the first one-dimensional parts placement and the second one-dimensional parts placement, (11) a layout mapping unit which maps, for each partition, parts placement to the partition by determining a quadrilateral including all the parts schematically placed by the two-dimensional part placing unit, and by transforming the quadrilateral to the partition, and (12) a partition dividing unit further divides the parts placement mapped by the layout mapping unit into a plurality of zones for each part, and places the parts in the divided zones.
Further, according to a third aspect of the invention, an automatic parts placement device which automatically places parts on two-dimensional parts placement zone is provided. The device comprises (1) a part data input device which inputs shapes and areas of the parts and net data of nets connecting between the parts, and stores them to a storage device, (2) an operational instruction input device which designates placement position of a position designated part in response to an operational instruction, (3) a cluster producing unit which produces a cluster including parts each of which has strong net connectivity, (4) a first parts specific gravity calculating unit which derives a parts specific gravity for each combination of a part and a parts group, (5) a parts group producing unit which adds a part to a parts group having a plurality of parts around the position designated part, (6) a re-distributing unit which moves a part from a current parts group to another parts group which has stronger connectivity to the part, (7) a partition producing unit which produces a rectangular shape of partition by dividing a parts placement zone according to a ratio of an area of the parts group, (8) a second one-dimensional parts specific gravity calculating unit calculates a parts specific gravity based on the number of nets connecting in the X-axis direction of the XY coordinate two-dimensional plane or in the Y-axis direction of the XY coordinate two-dimensional plane, (9) a second one-dimensional lining unit which lines the parts along the X-axis in order of the parts specific gravity to store the parts placement as first one-dimensional parts placement, and lines the parts along the Y-axis perpendicular to the X-axis in order of the parts specific gravity to store the parts placement as second one-dimensional parts placement, (10) a second two-dimensional part placing unit which schematically places the part on the XY coordinate two-dimensional plane using the first one-dimensional parts placement and the second one-dimensional parts placement, (11) a second partition dividing unit further divides the parts placement zone into a plurality of an individual part zones using a first lines parallel to the X-axis and a second lines parallel to the Y-axis, the lines being defined with the interval of the minimum area of the part, and (12) a parts replacing unit which replaces the part by moving the part to another individual part zone so that there is one or no part in every individual part are.
Further, according to a fourth aspect of the invention, a method of automatically placing parts is provided. The method comprises the steps of (a) inputting net data of a net connecting between terminals of parts, parts data, and position data of position designated parts, (b) deriving parts group from a plurality of parts, (c) producing a partition by dividing a parts placement zone into a plurality of partitions according to the total area of all the parts in the parts group, each partition having rectangular shape and being related to a parts group, (d) calculating a parts specific gravity of a undefined part, for each partition, by subtracting from the number of nets connecting between placed parts and the undefined part in the partition, the number of the other nets connected to the undefined part, and by dividing the result of subtracting by the area of the undefined part, (dxe2x80x2) determining a first one-dimensional parts placement by placing the un-placement parts nearby the placed part on a first one-dimensional axis in the descending order of the parts specific gravity, (e) determining a second one-dimensional parts placement by placing the undefined parts nearby the placed part on a second one-dimensional axis perpendicular to the first one-dimensional axis in the descending order of the parts specific gravity, and (f) determining parts placement on a two-dimensional plane by placing, for each partition, the undefined parts on a two-dimensional plane using the first one-dimensional parts placement and the second one-dimensional parts placement.
Further, according to a fifth aspect of the invention, a recording medium tangibly embodying a program of instructions executable by the computer to perform a method of automatically placing parts is provided. The method comprises the steps of (a) inputting net data of a net connecting between terminals of parts, parts data, and position data of position designated parts, (b) deriving parts group from a plurality of parts, (c) producing a partition by dividing a parts placement zone into a plurality of partitions according to the total area of all the parts in the parts group, each partition having rectangular shape and being related to a parts group, (d) calculating a parts specific gravity of a undefined part, for each partition, by subtracting from the number of nets connecting between placed parts and the undefined part in the partition, the number of the other nets connected to the undefined part, and by dividing the result of subtracting by the area of the undefined part, (dxe2x80x2) determining a first one-dimensional parts placement by placing the un-placement parts nearby the placed part on a first one-dimensional axis in the descending order of the parts specific gravity, (e) determining a second one-dimensional parts placement by placing the undefined parts nearby the placed part on a second one-dimensional axis perpendicular to the first one-dimensional axis in the descending order of the parts specific gravity, and (f) determining parts placement on a two-dimensional plane by placing, for each partition, the undefined parts on a two-dimensional plane using the first one-dimensional parts placement and the second one-dimensional parts placement.
The above described functions or processes are realized by programs executed on a computer. The programs may be supplied to the computer via an input device from a computer readable medium storing the programs. The programs are loaded to a main memory of the computer before execution.